{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Soup Servings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming #probability-and-statistics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划 #概率与统计"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: soupServings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分汤"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有&nbsp;<strong>A&nbsp;和&nbsp;B 两种类型&nbsp;</strong>的汤。一开始每种类型的汤有&nbsp;<code>n</code>&nbsp;毫升。有四种分配操作：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>提供 <code>100ml</code> 的 <strong>汤A</strong> 和 <code>0ml</code> 的 <strong>汤B</strong> 。</li>\n",
    "\t<li>提供 <code>75ml</code> 的 <strong>汤A</strong> 和 <code>25ml</code> 的 <strong>汤B</strong> 。</li>\n",
    "\t<li>提供 <code>50ml</code> 的 <strong>汤A</strong> 和 <code>50ml</code> 的 <strong>汤B</strong> 。</li>\n",
    "\t<li>提供 <code>25ml</code> 的 <strong>汤A</strong> 和 <code>75ml</code> 的 <strong>汤B</strong> 。</li>\n",
    "</ol>\n",
    "\n",
    "<p>当我们把汤分配给某人之后，汤就没有了。每个回合，我们将从四种概率同为 <code>0.25</code> 的操作中进行分配选择。如果汤的剩余量不足以完成某次操作，我们将尽可能分配。当两种类型的汤都分配完时，停止操作。</p>\n",
    "\n",
    "<p><strong>注意&nbsp;</strong>不存在先分配 <code>100</code> ml <strong>汤B</strong> 的操作。</p>\n",
    "\n",
    "<p>需要返回的值：&nbsp;<strong>汤A&nbsp;</strong>先分配完的概率 +&nbsp;&nbsp;<strong>汤A和汤B&nbsp;</strong>同时分配完的概率 / 2。返回值在正确答案&nbsp;<code>10<sup>-5</sup></code>&nbsp;的范围内将被认为是正确的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 50\n",
    "<strong>输出:</strong> 0.62500\n",
    "<strong>解释:</strong>如果我们选择前两个操作<strong>，</strong>A 首先将变为空。\n",
    "对于第三个操作，A 和 B 会同时变为空。\n",
    "对于第四个操作，B 首先将变为空。<strong>\n",
    "</strong>所以 A 变为空的总概率加上 A 和 B 同时变为空的概率的一半是 0.25 *(1 + 1 + 0.5 + 0)= 0.625。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 100\n",
    "<strong>输出:</strong> 0.71875\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= n &lt;= 10<sup>9</sup></code>​​​​​​​</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [soup-servings](https://leetcode.cn/problems/soup-servings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [soup-servings](https://leetcode.cn/problems/soup-servings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['50', '100']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        n=(n+24)//25\n",
    "        if n==0:return 0.5\n",
    "        if n>200:return 1\n",
    "        dp=[[0]*(n+1) for i in range(n+1)]\n",
    "        dp[0][0]=1\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if dp[i][j]:\n",
    "                    for a,b in [(4,0),(3,1),(2,2),(1,3)]:\n",
    "                        if j+b>=n and i+a>=n:\n",
    "                            ans+=dp[i][j]*0.25/2\n",
    "                        elif i+a>=n:\n",
    "                            ans+=dp[i][j]*0.25\n",
    "                        elif j+b<n:dp[i+a][j+b]+=dp[i][j]*0.25\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        n = min(179, int(math.ceil(n / 25)))\n",
    "        dp = [[0] * (n+1) for _ in range(n+1)]\n",
    "        dp[0][0] = 0.5\n",
    "\n",
    "        for j in range(1, n+1):\n",
    "            dp[0][j] = 1\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, n+1):\n",
    "                dp[i][j] = 0.25 * (dp[max(0, i-4)][j] + dp[max(0, i-3)][j-1] + dp[max(0, i-2)][max(0, j-2)] + dp[i-1][max(0, j-3)])\n",
    "\n",
    "        return dp[n][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        visiting = deque([(n,n)])\n",
    "        visiting_dic = {(n,n):1}\n",
    "        delta_list = [(-100,0),(-75,-25),(-50,-50),(-25,-75)]\n",
    "        visited_dic = {}\n",
    "        prob = 0\n",
    "        round = 1\n",
    "        if n > 5000:\n",
    "            return 1\n",
    "        while visiting or visited_dic:\n",
    "            while visiting:\n",
    "                pos = visiting.pop()\n",
    "                coef = visiting_dic[pos]\n",
    "                for delta in delta_list:\n",
    "                    new_pos = (pos[0]+delta[0],pos[1]+delta[1])\n",
    "                    if new_pos[0] <=0:\n",
    "                        if new_pos[1] >0:\n",
    "                            prob += coef *((0.25)**(round))\n",
    "                        else:\n",
    "                            prob += coef/2 *((0.25)**(round))\n",
    "\n",
    "                    elif new_pos[1] > 0:\n",
    "                        visited_dic[new_pos] = visited_dic.get(new_pos,0)+ coef\n",
    "            round += 1\n",
    "            \n",
    "            visiting = deque(visited_dic.keys())\n",
    "            visiting_dic = visited_dic\n",
    "            visited_dic = {}\n",
    "        \n",
    "        return prob\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        n = (n+24)//25\n",
    "        if n >= 179:\n",
    "            return 1.0\n",
    "        afirst = [[-1] *(n+1) for _ in range(n+1)]\n",
    "        def help1(a,b):\n",
    "            a, b = max(0,a), max(0,b)\n",
    "            if afirst[a][b] == -1:\n",
    "                if a == 0 and b == 0:\n",
    "                    afirst[a][b] = 0.5\n",
    "                elif a == 0:\n",
    "                    afirst[a][b] = 1\n",
    "                elif b == 0:\n",
    "                    afirst[a][b] = 0                    \n",
    "                else:\n",
    "                    afirst[a][b] = 0.25*help1(a-4,b)+0.25*help1(a-3,b-1)+0.25*help1(a-2,b-2)+0.25*help1(a-1,b-3)\n",
    "            return afirst[a][b]\n",
    "        return help1(n,n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        if n >= 5000:\n",
    "            return 1.0\n",
    "        memo = {}\n",
    "        def Aempty(a, b):\n",
    "            if b == 0 and a > 0:\n",
    "                return 0\n",
    "            if a == 0:\n",
    "                return b > 0\n",
    "            if (a, b) in memo:\n",
    "                return memo[(a, b)]\n",
    "            ans = 0\n",
    "            for da, db in [[100, 0], [75, 25], [50, 50], [25, 75]]:\n",
    "                ans += Aempty(max(0, a-da), max(0, b-db))\n",
    "            ans /= 4\n",
    "            memo[(a,b)] = ans\n",
    "            return ans\n",
    "            \n",
    "        dic = {}\n",
    "        def ABempty(a, b):\n",
    "            if a == 0 and b == 0:\n",
    "                return 1\n",
    "            if a == 0 or b == 0:\n",
    "                return 0\n",
    "            if (a, b) in dic:\n",
    "                return dic[(a, b)]\n",
    "            ans = 0\n",
    "            for da, db in [[100, 0], [75, 25], [50, 50], [25, 75]]:\n",
    "                ans += ABempty(max(0, a-da), max(0, b-db))\n",
    "            ans /= 4\n",
    "            dic[(a,b)] = ans\n",
    "            return ans\n",
    "        \n",
    "        return Aempty(n, n) + ABempty(n, n)/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        n = (n + 24) // 25\n",
    "        if n >= 500: return 1\n",
    "        memo = {}\n",
    "        def dp(a, b):\n",
    "            if (a, b) in memo: return memo[(a, b)]\n",
    "            if a <= 0 and b <= 0: return 0.5\n",
    "            if a <= 0: return 1\n",
    "            if b <= 0: return 0\n",
    "            memo[(a, b)] = 0.25 * (dp(a - 4, b) + dp(a - 3, b - 1) + dp(a - 2, b - 2) + dp(a - 1, b - 3))\n",
    "            return memo[(a, b)]\n",
    "        return dp(n, n)\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        n = min(200, math.ceil(n / 25))\n",
    "        f = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        f[0][0] = 0.5\n",
    "        for j in range(1, n + 1):\n",
    "            f[0][j] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                a = f[max(i - 4, 0)][j]\n",
    "                b = f[max(i - 3, 0)][max(j - 1, 0)]\n",
    "                c = f[max(i - 2, 0)][max(j - 2, 0)]\n",
    "                d = f[max(i - 1, 0)][max(j - 3, 0)]\n",
    "                f[i][j] = 0.25 * (a + b + c + d)\n",
    "        return f[n][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # dp(i, j) = 0.25 * (dp(i-4, j) + dp(i-3, j-1) + dp(i-2, j-2) + dp(i-1,j-3))\n",
    "    # i == 0， j > 0 时, dp = 1\n",
    "    # i == 0, j == 0 时, dp = 0.5\n",
    "    # i > 0, j == 0 时, dp = 0\n",
    "    def dfs(self, i, j):\n",
    "        if i <= 0 and j <= 0:\n",
    "            return 0.5\n",
    "        if i <= 0:\n",
    "            return 1\n",
    "        if j <= 0:\n",
    "            return 0\n",
    "        if self.memo[i][j] != -1:\n",
    "            return self.memo[i][j]\n",
    "        self.memo[i][j] = 0.25 * (self.dfs(i-4, j) + self.dfs(i-3, j-1) + self.dfs(i-2, j-2) + self.dfs(i-1, j-3))\n",
    "        return self.memo[i][j]\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        n_ = (n + 24) // 25\n",
    "        if n_ >= 179:\n",
    "            return 1\n",
    "        self.memo = [[-1] * (n_+1) for _ in range(n_ + 1)]\n",
    "        return self.dfs(n_, n_)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def soupServings(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        n = ceil(n / 25.0)\n",
    "        if n >= 179:\n",
    "            return 1.0\n",
    "        @cache\n",
    "        def DFS(a, b):\n",
    "            if a <= 0 and b <= 0:\n",
    "                return 0.5\n",
    "            elif a <= 0:\n",
    "                return 1.0\n",
    "            elif b <= 0:\n",
    "                return 0.0\n",
    "            res = 1.0 / 4.0 *(DFS(a - 4, b) + DFS(a - 3, b - 1) + DFS(a- 2, b - 2) + DFS(a - 1, b - 3))\n",
    "            return res\n",
    "        return DFS(n,n)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        n = (n + 24) // 25\n",
    "        if n >= 179: return 1.\n",
    "        @cache\n",
    "        def dfs(a, b):\n",
    "            if a <= 0 and b <= 0:\n",
    "                return 0.5\n",
    "            if a <=0: return 1.\n",
    "            if b <= 0: return 0.\n",
    "            return (dfs(a - 4, b) + dfs(a - 3, b - 1) + dfs(a - 2, b - 2) + dfs(a - 1, b - 3)) / 4\n",
    "        return dfs(n, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        n = (n + 24) // 25\n",
    "        if n >= 179:\n",
    "            return 1.0\n",
    "        dp = [[0.0] * (n + 1) for _ in range(n + 1)]\n",
    "        dp[0] = [0.5] + [1.0] * n\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                dp[i][j] = (dp[max(0, i - 4)][j] + dp[max(0, i - 3)][max(0, j - 1)] +\n",
    "                            dp[max(0, i - 2)][max(0, j - 2)] + dp[max(0, i - 1)][max(0, j - 3)]) / 4\n",
    "        return dp[n][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i <= 0 and j <= 0:\n",
    "                return 0.5\n",
    "            if i <= 0:\n",
    "                return 1\n",
    "            if j <= 0:\n",
    "                return 0\n",
    "            return 0.25 * (dfs(i - 4, j) + dfs(i - 3, j - 1) + dfs(i - 2, j - 2) + dfs(i - 1, j - 3))\n",
    "        \n",
    "        return 1 if n > 4800 else dfs((n + 24) // 25, (n + 24) // 25)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        if n > 5000:\n",
    "            return 1\n",
    "        @cache\n",
    "        def find(x, y):\n",
    "            if x <= 0 and y <= 0:\n",
    "                return 0.5\n",
    "            if x <= 0:\n",
    "                return 1\n",
    "            if y <= 0:\n",
    "                return 0\n",
    "            \n",
    "            ans = find(x-100, y) + find(x-75,y-25) + find(x-50,y-50)+find(x-25,y-75)\n",
    "            return ans / 4\n",
    "\n",
    "        return find(n, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        # 都是25倍数，先缩小\n",
    "        # choices = [(4,0), (3,1), (2,2), (1,3)] # 四种分配\n",
    "        n_0 = (n+24)//25 + 1 \n",
    "        if n_0 > 180:\n",
    "            return 1\n",
    "        # 因为dp[i][j]明显超时，但是，，，由于是概率题，在0.9999以上即为1\n",
    "        # 当n巨大，每轮a的 E= （4+3+2+1）*0.25 = 2.5， b E = (1+2+3)*0.25 = 1.5\n",
    "        # 先取完b的概率小于 0.00001，答案说179*25以上就可以返回1了，暂取这个\n",
    "        # dp[i][j] 表示一开始给多少a 多少b\n",
    "        dp = [[0] * min(n_0+1,180) for _ in range(min(n_0+1,180))]\n",
    "        # bc\n",
    "        dp[0][0] = 1*0.5 # 一开始ab都没有\n",
    "        for c in range(1, min(n_0+1,180)):\n",
    "            dp[0][c] = 1\n",
    "\n",
    "        for i in range(1, min(n_0+1,180)):\n",
    "            for j in range(1, min(n_0+1,180)):\n",
    "                # transition from ...\n",
    "                dp[i][j] = 0.25* (dp[max(i-4, 0)][j] + dp[max(i-3, 0)][max(j-1, 0)] + dp[max(i-2, 0)][max(j-2, 0)] + dp[max(i-1, 0)][max(j-3, 0)]) # 为什么max，因为最后一点是可以分的，即使没到整数的量\n",
    "        \n",
    "        # print(dp)\n",
    "        # print(n_0)\n",
    "        return dp[n_0-1][n_0-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        if n >= 5000:\n",
    "            return 1\n",
    "\n",
    "        nLen = n // 25 * 2 + 2\n",
    "\n",
    "        dp = [[-1.0 for _ in range(nLen)] for _ in range(nLen)]\n",
    "\n",
    "        def dfs(r, c):\n",
    "            if r <= 0:\n",
    "                if c <= 0:\n",
    "                    return 0.5\n",
    "                else:\n",
    "                    return 1.0\n",
    "            else:\n",
    "                if c <= 0:\n",
    "                    return 0  \n",
    "\n",
    "            row = r // 25 + 1 if r % 25 > 0 else r // 25\n",
    "            col = c // 25 + 1 if c % 25 > 0 else c // 25\n",
    "            if dp[row][col] < -0.5:\n",
    "                dp[row][col] = 0\n",
    "                dp[row][col] += dfs(r - 100, c)\n",
    "                dp[row][col] += dfs(r - 75, c - 25)\n",
    "                dp[row][col] += dfs(r - 50, c - 50)\n",
    "                dp[row][col] += dfs(r - 25, c - 75)\n",
    "                dp[row][col] /= 4\n",
    "\n",
    "            return dp[row][col]\n",
    "\n",
    "        ans = dfs(n,n)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        n = (n + 24) // 25\n",
    "        if n >= 179:\n",
    "            return 1.0\n",
    "        \n",
    "        dp = [[0.0] * (n + 1) for _ in range(n + 1)]\n",
    "        dp[0] = [0.5] + [1.0] * n\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                dp[i][j] = (dp[max(0, i - 4)][j] + dp[max(0, i - 3)][max(0, j - 1)] + dp[max(0, i - 2)][max(0, j - 2)] + dp[max(0, i - 1)][max(0, j - 3)]) / 4\n",
    "\n",
    "        return dp[n][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        n = (n+24)//25\n",
    "        if n>= 179:\n",
    "            return 1.0\n",
    "        plans = [(4,0),(3,1),(2,2),(1,3)]\n",
    "        dp = [[0]*(n+1) for _ in range(n+1)]\n",
    "        dp[0][0] = 0.5\n",
    "        for j in range(1,n+1):\n",
    "            dp[0][j] = 1\n",
    "        \n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,n+1):\n",
    "                for dx, dy in plans:\n",
    "                    dp[i][j] += 0.25*dp[max(i-dx,0)][max(j-dy,0)]\n",
    "\n",
    "\n",
    "        \n",
    "        return dp[n][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        m = (n + 24) // 25\n",
    "\n",
    "        if m >= 179:\n",
    "            return 1\n",
    "\n",
    "        memo = [[0.0] * (m + 1) for _ in range(m + 1)]\n",
    "        \n",
    "        def dp(a, b):\n",
    "            if a <= 0 and b <= 0:\n",
    "                return 0.5\n",
    "            if a <= 0:\n",
    "                return 1\n",
    "            if b <= 0:\n",
    "                return 0\n",
    "            \n",
    "            if memo[a][b] == 0:\n",
    "                memo[a][b] = 0.25 * (dp(a - 4, b) + dp(a - 3, b - 1) + dp(a - 2, b - 2) + dp(a - 1, b - 3))\n",
    "\n",
    "            return memo[a][b]\n",
    "        \n",
    "        return dp(m, m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        n = (n + 24) // 25\n",
    "        if n >= 179:\n",
    "            return 1.0\n",
    "        f = [[0.0] * (n + 1) for _ in range(n + 1)]\n",
    "        f[0] = [0.5] + [1.0] * n\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                f[i][j] = (f[max(0, i - 4)][j] + f[max(0, i - 3)][max(0, j - 1)] + f[max(0, i - 2)][max(0, j - 2)] + f[max(0, i - 1)][max(0, j - 3)]) / 4\n",
    "        return f[n][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        n=(n+24)//25\n",
    "        if n>=179:\n",
    "            return 1.0\n",
    "        dp=[[0.0]*(n+1)for each in range(n+1)]\n",
    "        dp[0]=[0.5]+[1.0]*n\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,n+1):     \n",
    "                dp[i][j]=(dp[max(i-4,0)][j]+dp[max(i-3,0)][max(j-1,0)]+dp[max(i-2,0)][max(j-2,0)]+dp[max(i-1,0)][max(j-3,0)])/4\n",
    "\n",
    "        return dp[n][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        n=(n+24)//25\n",
    "        if n>=179:\n",
    "            return 1.0\n",
    "        dp=[[0.0]*(n+1) for _ in range(n+1)]\n",
    "        dp[0]=[0.5]+[1.0]*n\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,n+1):\n",
    "                dp[i][j]=(dp[max(0,i-4)][j]+dp[max(0,i-3)][max(0,j-1)]+dp[max(0,i-2)][max(0,j-2)]+dp[max(0,i-1)][max(0,j-3)])/4\n",
    "        return dp[n][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        n = (n + 24) // 25\n",
    "        if n >= 179:\n",
    "            return 1.0\n",
    "        \n",
    "        dp = [[0.0] * (n + 1) for _ in range(n + 1)]\n",
    "        dp[0] = [0.5] + [1.0] * n\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                dp[i][j] = (dp[max(0, i - 4)][j] + dp[max(0, i - 3)][max(0, j - 1)] + \n",
    "                            dp[max(0, i - 2)][max(0, j - 2)] + dp[max(0, i - 1)][max(0, j - 3)]) / 4\n",
    "        \n",
    "        return dp[n][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        \n",
    "        n = (n + 24) // 25\n",
    "\n",
    "        if n > 179:\n",
    "            return 1\n",
    "\n",
    "        dp = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        \n",
    "        dp[0][0] = 0.5\n",
    "\n",
    "        for j in range(1, n + 1):\n",
    "            dp[0][j] =  1\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                dp[i][j] = 1 / 4 * (dp[max(i - 4, 0)][j] + dp[max(i - 3, 0)][max(j - 1, 0)]\\\n",
    "                           + dp[max(i - 2, 0)][max(j - 2, 0)] + dp[max(i - 1, 0)][max(j - 3, 0)])\n",
    "        \n",
    "        return dp[n][n]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        if n>=4475:\n",
    "            return 1\n",
    "        k=(n//25)+1 if n%25!=0 else n//25\n",
    "\n",
    "        dp=[[0]*(k+1) for _ in range(k+1)]\n",
    "\n",
    "        dp[0][0]=0.5\n",
    "\n",
    "        for i in range(1,k+1):\n",
    "            dp[0][i]=1\n",
    "\n",
    "        \n",
    "        \n",
    "        for i in range(1,k+1):\n",
    "            for j in range(1,k+1):\n",
    "                dp[i][j]+=dp[max(i-4,0)][j] \n",
    "                dp[i][j]+=dp[max(i-3,0)][j-1]\n",
    "                dp[i][j]+=dp[max(i-2,0)][max(j-2,0)] \n",
    "                dp[i][j]+=dp[i-1][max(j-3,0)] \n",
    "                dp[i][j]*=0.25\n",
    "        \n",
    "        return dp[k][k]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        n = (n+24) // 25\n",
    "        if n >= 179:\n",
    "            return 1\n",
    "        dp = [[0.0] * (n+1) for _ in range(n+1)]\n",
    "        dp[0] = [0.5] + [1.0] * n\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, n+1):\n",
    "                dp[i][j] = (dp[max(0, i - 4)][j] + dp[max(0, i - 3)][max(0, j - 1)] +\n",
    "                            dp[max(0, i - 2)][max(0, j - 2)] + dp[max(0, i - 1)][max(0, j - 3)]) / 4\n",
    "        return dp[n][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        n = min(200, math.ceil(n/25))\n",
    "\n",
    "        dp = [[0] * (n+1) for i in range(n+1)]\n",
    "\n",
    "        dp[0][0] = 0.5\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            dp[0][i] = 1\n",
    "            \n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,n+1):\n",
    "                dp[i][j] = 0.25 * (dp[max(i-4, 0)][j] + dp[max(i-3, 0)][max(j-1, 0)] + dp[max(i-2, 0)][max(j-2, 0)] + \n",
    "                                dp[max(i-1, 0)][max(j-3, 0)])\n",
    "\n",
    "\n",
    "        return dp[n][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dr = [[-4,0], [-3, -3], [-2,-2],[-1,-3]]\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        n = min(200, math.ceil(n / 25))\n",
    "        f = [[0] *(n+10) for _ in range(n+10)]\n",
    "\n",
    "        f[0][0] = 0.5\n",
    "\n",
    "        for i in range(1, n+10):\n",
    "            f[0][i] = 1\n",
    "\n",
    "        for i in range(1, 1+n):\n",
    "            for j in range(1, 1+n):\n",
    "                a, b = f[max(i - 4, 0)][j], f[max(i - 3, 0)][max(j - 1, 0)]\n",
    "                c, d = f[max(i - 2, 0)][max(j - 2, 0)], f[max(i - 1, 0)][max(j - 3, 0)]\n",
    "                f[i][j] = 0.25 *(a+b+c+d)\n",
    "        return f[n][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        n = min(200, math.ceil(n/25))\n",
    "        f = [[0] * (n + 10) for _ in range(n + 10)]\n",
    "        f[0][0] = 0.5\n",
    "        for j in range(1, n + 10):\n",
    "            f[0][j] = 1\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, n+1):\n",
    "                a, b = f[max(i - 4, 0)][j], f[max(i - 3, 0)][max(j - 1, 0)]\n",
    "                c, d = f[max(i - 2, 0)][max(j - 2, 0)], f[max(i - 1, 0)][max(j - 3, 0)]\n",
    "                f[i][j] = 0.25*(a+b+c+d)\n",
    "        return f[n][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "\n",
    "        m = (n+24)//25\n",
    "        if m>=400:\n",
    "            return 1\n",
    "        dp = [[0]*(m+1) for _ in range(m+1)]\n",
    "        dp[0][0] = 0.5\n",
    "        for i in range(1,m+1):\n",
    "            dp[0][i] = 1\n",
    "\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,m+1):\n",
    "                p1 = dp[max(0,i-4)][j]\n",
    "                p2 = dp[max(0,i-3)][max(0,j-1)]\n",
    "                p3 = dp[max(0,i-2)][max(0,j-2)]\n",
    "                p4 = dp[max(0,i-1)][max(0,j-3)]\n",
    "                dp[i][j] = 0.25*(p1+p2+p3+p4)\n",
    "        \n",
    "\n",
    "        \n",
    "        return dp[m][m]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n:int)->float:\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i<=0 and j<=0:\n",
    "                return 0.5\n",
    "            elif i<=0:\n",
    "                return 1\n",
    "            elif j<=0:\n",
    "                return 0\n",
    "            else:\n",
    "                return 0.25*(dfs(i-4, j)+dfs(i-3,j-1)+dfs(i-2,j-2)+dfs(i-1,j-3))\n",
    "\n",
    "        return 1 if n>4800 else dfs(math.ceil(n/25), math.ceil(n/25))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        if n > 4800:\n",
    "            return 1\n",
    "        a = (n+24) // 25\n",
    "        b = (n+24) // 25\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i <= 0 and j <= 0:\n",
    "                return 0.5\n",
    "            if i <= 0:\n",
    "                return 1\n",
    "            if j <= 0:\n",
    "                return 0\n",
    "            return (dfs(i-4, j) + dfs(i-3, j-1) + dfs(i-2, j-2) + dfs(i-1, j-3)) * 0.25\n",
    "        return dfs(a, b)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        n=(n+24)//25\n",
    "        if n>=179:\n",
    "            return 1.0\n",
    "        @cache\n",
    "        def dfs(a:int,b:int)->float:\n",
    "            if a<=0 and b<=0:\n",
    "                return 0.5\n",
    "            if a<=0:\n",
    "                return 1.0\n",
    "            if b<=0:\n",
    "                return 0.0\n",
    "            return(dfs(a-4,b)+dfs(a-3,b-1)+dfs(a-2,b-2)+dfs(a-1,b-3))/4\n",
    "        return dfs(n,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i <= 0 and j <= 0:\n",
    "                return 0.5\n",
    "            if i <= 0:\n",
    "                return 1\n",
    "            if j <= 0:\n",
    "                return 0\n",
    "            return 0.25 * (dfs(i - 4, j) + dfs(i - 3, j - 1) + dfs(i - 2, j - 2) + dfs(i - 1, j - 3))\n",
    "        \n",
    "        return 1 if n > 4800 else dfs((n + 24) // 25, (n + 24) // 25)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def soupServings(self, N):\n",
    "        Q, R = divmod(N, 25)\n",
    "        N = Q + (R > 0)\n",
    "        if N >= 500: return 1\n",
    "\n",
    "        memo = {}\n",
    "        @lru_cache(None)\n",
    "        def dp(x, y):\n",
    "            if (x, y) not in memo:\n",
    "                if x <= 0 or y <= 0:\n",
    "                    ans = 0.5 if x<=0 and y<=0 else 1.0 if x<=0 else 0.0\n",
    "                else:\n",
    "                    ans = 0.25 * (dp(x-4,y)+dp(x-3,y-1)+dp(x-2,y-2)+dp(x-1,y-3))\n",
    "                memo[x, y] = ans\n",
    "            return memo[x, y]\n",
    "\n",
    "        return dp(N, N)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 这个破题原则上可以蒙特卡洛，树形遍历解空间，然后用离散概率（整数除法）。\n",
    "    # 但是这似乎是一个DP题。\n",
    "    # 不好想，我想想。\n",
    "\n",
    "    # 答案：解空间有限，也就意味着基本可以用记忆化搜索做。疑似可以用DP做，做法大概是：\n",
    "    # 自底向上，遍历有限的解空间。而dp(i, j)储存结局1、2的概率p1 p2，而dp(i, j) p1 = 1/4(sum(四种子操作p1)/4)\n",
    "    # 实际上利用了贝叶斯公式。\n",
    "\n",
    "    # 显然，记忆化搜索不会差，和DP复杂度相似。那么还是用记忆化搜索，这向来会是我的首选，因为便于理解。\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        if n == 0:\n",
    "            return 0.5\n",
    "        if n >= 4475:\n",
    "            return 1.0\n",
    "        self.mem = {}\n",
    "        p1, p2 = self.search(n, n)\n",
    "        return p1 + p2/2\n",
    "\n",
    "\n",
    "    def search(self, va, vb):\n",
    "        print(f\"va{va}, vb{vb}\")\n",
    "        if va == 0 and vb == 0:\n",
    "            return 0.0 , 1.0\n",
    "        if va == 0 and vb > 0:\n",
    "            return 1.0 , 0.0\n",
    "        if va > 0 and vb == 0:\n",
    "            return 0.0 , 0.0\n",
    "        if (va, vb) in self.mem:\n",
    "            return self.mem[(va, vb)]\n",
    "            \n",
    "        p1, p2 = 0, 0\n",
    "        if va <= 100:\n",
    "            r11, r12 = self.search(0, vb)\n",
    "            p1 += r11 * 0.25\n",
    "            p2 += r12 * 0.25\n",
    "        else:\n",
    "            r11, r12 = self.search(va-100, vb)\n",
    "            p1 += r11 * 0.25\n",
    "            p2 += r12 * 0.25\n",
    "\n",
    "        if va <= 75 and vb <= 25:\n",
    "            r11, r12 = self.search(0, 0)\n",
    "            p1 += r11 * 0.25\n",
    "            p2 += r12 * 0.25\n",
    "        elif va <= 75 and vb > 25:\n",
    "            r11, r12 = self.search(0, vb-25)\n",
    "            p1 += r11 * 0.25\n",
    "            p2 += r12 * 0.25\n",
    "        elif va > 75 and vb <= 25:\n",
    "            r11, r12 = self.search(va-75, 0)\n",
    "            p1 += r11 * 0.25\n",
    "            p2 += r12 * 0.25\n",
    "        else:\n",
    "            r11, r12 = self.search(va-75, vb-25)\n",
    "            p1 += r11 * 0.25\n",
    "            p2 += r12 * 0.25\n",
    "\n",
    "        if va <= 50 and vb <= 50:\n",
    "            r11, r12 = self.search(0, 0)\n",
    "            p1 += r11 * 0.25\n",
    "            p2 += r12 * 0.25\n",
    "        elif va <= 50 and vb > 50:\n",
    "            r11, r12 = self.search(0, vb-50)\n",
    "            p1 += r11 * 0.25\n",
    "            p2 += r12 * 0.25\n",
    "        elif va > 50 and vb <= 50:\n",
    "            r11, r12 = self.search(va-50, 0)\n",
    "            p1 += r11 * 0.25\n",
    "            p2 += r12 * 0.25\n",
    "        else:\n",
    "            r11, r12 = self.search(va-50, vb-50)\n",
    "            p1 += r11 * 0.25\n",
    "            p2 += r12 * 0.25\n",
    "\n",
    "        if va <= 25 and vb <= 75:\n",
    "            r11, r12 = self.search(0, 0)\n",
    "            p1 += r11 * 0.25\n",
    "            p2 += r12 * 0.25\n",
    "        elif va <= 25 and vb > 75:\n",
    "            r11, r12 = self.search(0, vb-75)\n",
    "            p1 += r11 * 0.25\n",
    "            p2 += r12 * 0.25\n",
    "        elif va > 25 and vb <= 75:\n",
    "            r11, r12 = self.search(va-25, 0)\n",
    "            p1 += r11 * 0.25\n",
    "            p2 += r12 * 0.25\n",
    "        else:\n",
    "            r11, r12 = self.search(va-25, vb-75)\n",
    "            p1 += r11 * 0.25\n",
    "            p2 += r12 * 0.25\n",
    "        \n",
    "        self.mem[(va,vb)] = (p1,p2)\n",
    "        return p1,p2\n",
    "        \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        if n>=179*25:\n",
    "            return 1       \n",
    "        # @cache\n",
    "        def f(x,y):\n",
    "            if (x,y) in dp:\n",
    "                return dp[(x,y)]\n",
    "            if x<=0 and y<=0:\n",
    "                return 0.5\n",
    "            if x<=0:\n",
    "                return 1\n",
    "            if y<=0:\n",
    "                return 0\n",
    "            else:\n",
    "                dp[(x,y)]=0.25*(f(x-4,y)+f(x-3,y-1)+f(x-2,y-2)+f(x-1,y-3))\n",
    "                return dp[(x,y)]\n",
    "        n = (n + 24) // 25\n",
    "        dp=dict()\n",
    "        return f(n,n)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def soupServings(self, n: int) -> float:\n",
    "    if n >5000:return 1.0\n",
    "    @lru_cache(None)\n",
    "    def dfs(a, b):\n",
    "      if a <= 0 and b <= 0:\n",
    "        return 0.5\n",
    "      if a <= 0:\n",
    "        return 1\n",
    "      if b <= 0:\n",
    "        return 0\n",
    "      return (dfs(a - 100, b) + dfs(a - 75, b - 25) + dfs(a - 50, b - 50) +\n",
    "              dfs(a - 25, b - 75)) / 4\n",
    "\n",
    "    return dfs(n, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from functools import cache\r\n",
    "class Solution:\r\n",
    "    def soupServings(self, n: int) -> float:\r\n",
    "        cache={}\r\n",
    "        if n>=4475:\r\n",
    "            return 1.0\r\n",
    "        def distribute(a,b):            \r\n",
    "            ops=[[100,0],[75,25],[50,50],[25,75]]\r\n",
    "            if a==b==0:\r\n",
    "                return 0.5\r\n",
    "            if a==0:\r\n",
    "                return 1\r\n",
    "\r\n",
    "            if b==0:\r\n",
    "                return 0\r\n",
    "            if (a,b) in cache:\r\n",
    "                return cache[(a,b)]\r\n",
    "            ret=0\r\n",
    "            for i in range(4):\r\n",
    "                na=max(0,a-ops[i][0])\r\n",
    "                nb=max(0,b-ops[i][1])\r\n",
    "                ret+=distribute(na,nb)/4\r\n",
    "            cache[(a,b)]=ret\r\n",
    "            return ret\r\n",
    "        ret= distribute(n,n)\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        if n >= 5000:\n",
    "            return 1\n",
    "        @cache\n",
    "        def dfs(a, b):\n",
    "            if not a and b:\n",
    "                return 1\n",
    "            if not a and not b:\n",
    "                return 0.5\n",
    "            if a and not b:\n",
    "                return 0\n",
    "            res = 0\n",
    "            res += dfs(max(0, a - 100), b)\n",
    "            res += dfs(max(0, a - 75), max(0, b - 25))\n",
    "            res += dfs(max(0, a - 50), max(0, b - 50))\n",
    "            res += dfs(max(0, a - 25), max(0, b - 75))\n",
    "            return res * 0.25\n",
    "        return dfs(n, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        @cache\n",
    "        def choose(a, b):\n",
    "            if a <= 0:\n",
    "                return 1 if b > 0 else 0.5\n",
    "            elif b <= 0:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for i, j in scheme:\n",
    "                res += 0.25 * choose(a-i, b-j)\n",
    "            return res\n",
    "        \n",
    "        scheme = ((100, 0), (75, 25),\n",
    "                  (50, 50), (25, 75))\n",
    "        return 1 if n > 4800 else choose(n, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        memo = {}\n",
    "        def dfs(i, j):\n",
    "            if (i, j) in memo:\n",
    "                return memo[(i, j)]\n",
    "            if i <= 0 and j <= 0: # 两种汤都分配完了\n",
    "                return 0.5 \n",
    "            if i <= 0: # 汤 A 先分配完了，此时应该返回 1\n",
    "                return 1\n",
    "            if j <= 0: # 汤 B 先分配完了，此时应该返回 0\n",
    "                return 0\n",
    "            # 接下来，对于每一次操作，我们都有四种选择, 每一种选择的概率都是 0.25\n",
    "\n",
    "            res = 0.25 * (dfs(i -100, j) + dfs(i -75, j-25) + dfs(i -50, j-50) + dfs(i-25, j-75))\n",
    "            memo[(i, j)] = res\n",
    "            return res\n",
    "\n",
    "        return 1 if n > 5000 else dfs(n, n)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        if n >= 179 * 25:\n",
    "            return 1\n",
    "        @cache\n",
    "        def dfs(a, b):\n",
    "            a = max(a, 0)\n",
    "            b = max(b, 0)\n",
    "            if a == 0 and b == 0:\n",
    "                return 0.5\n",
    "            if a == 0:\n",
    "                return 1\n",
    "            if b == 0:\n",
    "                return 0\n",
    "            p1 = dfs(a - 100, b)\n",
    "            p2 = dfs(a - 75, b - 25)\n",
    "            p3 = dfs(a - 50, b - 50)\n",
    "            p4 = dfs(a - 25, b - 75)\n",
    "            return 0.25 * (p1 + p2 + p3 + p4)\n",
    "        return dfs(n, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, N: int) -> float:\n",
    "        @functools.lru_cache(None)\n",
    "        def recurse(A, B):\n",
    "            if A==0 and B==0:\n",
    "                return 0, 1\n",
    "            if A==0:\n",
    "                return 1, 0\n",
    "            if B==0:\n",
    "                return 0, 0\n",
    "            \n",
    "            A1, B1 = recurse(max(0,A-100), B)\n",
    "            A2, B2 = recurse(max(0,A-75), max(0,B-25))\n",
    "            A3, B3 = recurse(max(0,A-50), max(0,B-50))\n",
    "            A4, B4 = recurse(max(0,A-25), max(0,B-75))\n",
    "\n",
    "            return 0.25*(A1+A2+A3+A4), 0.25*(B1+B2+B3+B4)\n",
    "        if (N//25+(N%25>0))>500:\n",
    "            return 1\n",
    "\n",
    "        A,B = recurse(N,N)\n",
    "\n",
    "        return A+B/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        @cache\n",
    "        def serve(a,b):\n",
    "            if a == 0:\n",
    "                if b == 0:\n",
    "                    return 0.5\n",
    "                else:\n",
    "                    return 1.\n",
    "            else:\n",
    "                if b == 0:\n",
    "                    return 0.\n",
    "                else:\n",
    "                    return 0.25*serve(max(a-100,0),b) + \\\n",
    "                           0.25*serve(max(a-75,0),max(b-25,0)) + \\\n",
    "                           0.25*serve(max(a-50,0),max(b-50,0)) + \\\n",
    "                           0.25*serve(max(a-25,0),max(b-75,0))\n",
    "        \n",
    "        if n >= 10000:\n",
    "            return 1.\n",
    "        return serve(n,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        if n > 5000:\n",
    "            return 1\n",
    "        memo = {}\n",
    "\n",
    "        def dp(a, b):\n",
    "            if a <= 0 and b <= 0: return 0.5\n",
    "            if a <= 0: return 1\n",
    "            if b <= 0: return 0\n",
    "            if (a, b) in memo: return memo[(a, b)]\n",
    "\n",
    "            prob = (dp(a - 100, b) + dp(a - 75, b - 25) + dp(a - 50, b - 50) + dp(a - 25, b - 75)) / 4.0\n",
    "            memo[(a, b)] = prob\n",
    "            return prob\n",
    "        \n",
    "        return dp(n, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        dp_memo = {'0, 0': 0.5, '0, 1': 1.0, '1, 0': 0.0}\n",
    "        num = int(n//25) + (n%25 > 0)\n",
    "        if num > 500:\n",
    "            return 1\n",
    "        def dp(x, y):\n",
    "            if x <= 0 and y <= 0:\n",
    "                return dp_memo['0, 0']\n",
    "            if x <= 0 and y > 0:\n",
    "                return dp_memo['0, 1']\n",
    "            if x > 0 and y <= 0:\n",
    "                return dp_memo['1, 0']\n",
    "            if dp_memo.get(f'{x}, {y}') is None:\n",
    "                dp_memo[f'{x}, {y}'] = 0.25 * (dp(x-4, y) + dp(x-3, y-1) + dp(x-2, y-2) + dp(x-1, y-3))\n",
    "                return dp_memo[f'{x}, {y}']\n",
    "            else:\n",
    "                return dp_memo[f'{x}, {y}']\n",
    "        for i in range(num+1):\n",
    "            dp(i, i)\n",
    "        return dp_memo[f'{num}, {num}']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "\n",
    "        # 返回A=i, B=j时的概率\n",
    "        @lru_cache(None)\n",
    "        def dp(i, j):\n",
    "            if i <= 0 and j <= 0:\n",
    "                return 0.5\n",
    "            if i <= 0:\n",
    "                return 1\n",
    "            if j <= 0:\n",
    "                return 0\n",
    "\n",
    "            return (dp(i-100, j) + dp(i-75, j-25) + dp(i-50, j-50) + dp(i-25, j-75)) / 4\n",
    "            \n",
    "        return dp(n, n) if n < 10000 else 1.0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        if n>=10000:\n",
    "            return 1.0\n",
    "\n",
    "        @cache\n",
    "        def dfs(a, b) -> Tuple:\n",
    "            if a <= 0:\n",
    "                return (1, 0) if b > 0 else (0, 1)\n",
    "            if b <= 0:\n",
    "                return 0, 0\n",
    "            x1, y1 = dfs(a - 100, b)\n",
    "            x2, y2 = dfs(a - 75, b - 25)\n",
    "            x3, y3 = dfs(a - 50, b - 50)\n",
    "            x4, y4 = dfs(a - 25, b - 75)\n",
    "            return ((x1 + x2 + x3 + x4) * 0.25, (y1 + y2 + y3 + y4) * 0.25)\n",
    "\n",
    "        # 需要返回的值： 汤A 先分配完的概率 +  汤A和汤B 同时分配完的概率 / 2。\n",
    "        p1, p2 = dfs(n, n)\n",
    "        return p1 + p2 / 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def dfs(self, a: int, b: int) -> float:\n",
    "        if a <= 0:\n",
    "            return 1.0 if b > 0 else 0.5\n",
    "        if b <= 0:\n",
    "            return 0.0\n",
    "\n",
    "\n",
    "        return (self.dfs(a - 100, b) + self.dfs(a - 75, b - 25) + self.dfs(a - 50, b - 50) + self.dfs(a - 25, b - 75)) / 4\n",
    "\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        if n >= 5000:\n",
    "            return 1.0\n",
    "\n",
    "        return self.dfs(n, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "from typing import Tuple\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        if n>=10000:\n",
    "            return 1.0\n",
    "\n",
    "        @cache\n",
    "        def dfs(a, b) -> Tuple:\n",
    "            if a <= 0:\n",
    "                return (1, 0) if b > 0 else (0, 1)\n",
    "            if b <= 0:\n",
    "                return 0, 0\n",
    "            x1, y1 = dfs(a - 100, b)\n",
    "            x2, y2 = dfs(a - 75, b - 25)\n",
    "            x3, y3 = dfs(a - 50, b - 50)\n",
    "            x4, y4 = dfs(a - 25, b - 75)\n",
    "            return ((x1 + x2 + x3 + x4) * 0.25, (y1 + y2 + y3 + y4) * 0.25)\n",
    "\n",
    "        # 需要返回的值： 汤A 先分配完的概率 +  汤A和汤B 同时分配完的概率 / 2。\n",
    "        p1, p2 = dfs(n, n)\n",
    "        return p1 + p2 / 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        n = (n + 24) // 25\n",
    "        if n >= 179:\n",
    "            return 1.0\n",
    "        # dp:在剩余 i 毫升汤 A 和 j 毫升汤 B 的情况下，汤 A 先被倒完的概率。\n",
    "        dp = [[0.0] * (n + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 0.5\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i][0] = 1.0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                dp[i][j] = (dp[max(0, i - 4)][j] + dp[max(0, i - 3)][max(0, j - 1)] + \n",
    "                            dp[max(0, i - 2)][max(0, j - 2)] + dp[max(0, i - 1)][max(0, j - 3)]) / 4\n",
    "        print(dp)\n",
    "        return 1 - dp[n][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        if n >10000:\n",
    "            return 1\n",
    "        A = [0,0,0]\n",
    "        @lru_cache(None)\n",
    "        def helper(i,j,k):\n",
    "            if i <=0 and j <=0:\n",
    "                return 0,1/4**k,0\n",
    "            elif i <= 0:\n",
    "                return 1/4**k,0,0\n",
    "            elif j <= 0:\n",
    "                return 0,0,1/4**k\n",
    "            else:\n",
    "                a,b,c = helper(i-100,j,k+1)\n",
    "                d,e,f = helper(i-75,j-25,k+1)\n",
    "                g,h,l = helper(i-50,j-50,k+1)\n",
    "                m,n,o = helper(i-25,j-75,k+1)\n",
    "                return a+d+g+m,b+e+h+n,c+f+l+o\n",
    "        a,b,c = helper(n,n,0)\n",
    "      #  print(a,b,c)\n",
    "        return (a+b/2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        if n%25==0:\n",
    "            n=n//25\n",
    "        else:\n",
    "            n=n//25+1\n",
    "        if n>500:\n",
    "            return 1\n",
    "       # dp=[[0]*(n+1) for _ in range(n)]\n",
    "       # dp[0][0]=1\n",
    "        memo={}\n",
    "        def dfs(x,y):\n",
    "            if  (x,y) in memo:\n",
    "                return memo[(x,y)]\n",
    "            if x<=0 and y>0:\n",
    "                return 1\n",
    "            elif x<=0 and y<=0:\n",
    "                return 0.5\n",
    "            elif x>0 and y<=0:\n",
    "                return 0\n",
    "\n",
    "            ans=0\n",
    "            for a,b in [[4,0],[3,1],[2,2],[1,3]]:\n",
    "                ans+=dfs(x-a,y-b)*0.25\n",
    "            \n",
    "            memo[(x,y)]=ans\n",
    "            return ans \n",
    "        \n",
    "        return dfs(n,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        if n%25==0:\n",
    "            n=n//25\n",
    "        else:\n",
    "            n=n//25+1\n",
    "        if n>500:\n",
    "            return 1\n",
    "       # dp=[[0]*(n+1) for _ in range(n)]\n",
    "       # dp[0][0]=1\n",
    "        memo={}\n",
    "        def dfs(x,y):\n",
    "            if  (x,y) in memo:\n",
    "                return memo[(x,y)]\n",
    "            if x<=0 and y>0:\n",
    "                return 1\n",
    "            elif x<=0 and y<=0:\n",
    "                return 0.5\n",
    "            elif x>0 and y<=0:\n",
    "                return 0\n",
    "\n",
    "            ans=0\n",
    "            for a,b in [[4,0],[3,1],[2,2],[1,3]]:\n",
    "                ans+=dfs(x-a,y-b)*0.25\n",
    "            \n",
    "            memo[(x,y)]=ans\n",
    "            return ans \n",
    "        \n",
    "        return dfs(n,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dp(self, nA, nB):\n",
    "        if nA <= 0:\n",
    "            if nB <= 0:\n",
    "                return 0, 1\n",
    "            return 1, 0\n",
    "        ret = self.dpRet.get(((nA, nB)))\n",
    "        if ret is not None:\n",
    "            return ret\n",
    "\n",
    "        ret0 = 0\n",
    "        ret1 = 0\n",
    "\n",
    "        x, y = self.dp(nA - 100, nB)\n",
    "        ret0 += 0.25 * x\n",
    "        ret1 += 0.25 * y if nB > 0 else 0\n",
    "\n",
    "        x, y = self.dp(nA - 75, nB - 25)\n",
    "        ret0 += 0.25 * x\n",
    "        ret1 += 0.25 * y if nB > 0 else 0\n",
    "\n",
    "        x, y = self.dp(nA - 50, nB - 50)\n",
    "        ret0 += 0.25 * x\n",
    "        ret1 += 0.25 * y if nB > 0 else 0\n",
    "\n",
    "        x, y = self.dp(nA - 25, nB - 75)\n",
    "        ret0 += 0.25 * x\n",
    "        ret1 += 0.25 * y if nB > 0 else 0\n",
    "        \n",
    "        self.dpRet[(nA, nB)] = (ret0, ret1)\n",
    "        return ret0, ret1\n",
    "\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        if n >= 500 * 25:\n",
    "            return 1\n",
    "        self.dpRet = dict()\n",
    "        x, y = self.dp(n, n)\n",
    "        return x + y / 2\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        if n > 4160:\n",
    "            return 1\n",
    "        d = {}\n",
    "        N = (n + 24) // 25\n",
    "\n",
    "        def helper(i, j):\n",
    "            if i <= 0 < j:\n",
    "                return 1\n",
    "            if j <= 0 < i:\n",
    "                return 0\n",
    "            if i <= 0 and j <= 0:\n",
    "                return 0.5\n",
    "            if (i, j) in d:\n",
    "                return d[(i, j)]\n",
    "            p = (helper(i - 4, j) + helper(i - 3, j - 1) + helper(i - 2, j - 2) + helper(i - 1, j - 3)) / 4\n",
    "            d[(i, j)] = p\n",
    "            return p\n",
    "\n",
    "        for s in range(1, 2 * N):\n",
    "            for i in range(1, s):\n",
    "                helper(i, s - i)\n",
    "        return helper(N, N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        if n >= 4500:\n",
    "            return 1\n",
    "        strategies = [(100, 0), (75, 25), (50, 50), (25, 75)]\n",
    "        memo = {}\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(a, b, lc):\n",
    "            trials = [min(math.ceil(a / (s[0] + 1e-6)), math.ceil(b / (s[1] + 1e-6))) for s in strategies]\n",
    "            if f'{a}_{b}_{lc}' in memo:\n",
    "                return memo[f'{a}_{b}_{lc}']\n",
    "            if a <= 0 and b > 0:\n",
    "                return 1\n",
    "            if a <= 0 and b <= 0:\n",
    "                return 0.5\n",
    "            if a > 0 and b <= 0:\n",
    "                return 0\n",
    "            ps = []\n",
    "            for c, (tr, s) in enumerate(zip(trials, strategies)):\n",
    "                if c == lc:\n",
    "                    continue\n",
    "                for i in range(1, tr+1):\n",
    "                    ps.append(0.25 ** i * dfs(a - i * s[0], b - i * s[1], c))\n",
    "            memo[f'{a}_{b}_{lc}'] = sum(ps)\n",
    "            return memo[f'{a}_{b}_{lc}']\n",
    "        return dfs(n, n, -1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        m = (n+24)//25\n",
    "        m = min(200, m) \n",
    "        dp1 = [[0] * (m+1) for _ in range(m+1)]\n",
    "        dp2 = [[0] * (m+1) for _ in range(m+1)] \n",
    "        dp1[0][0] = 1\n",
    "        for i in range(1, m+1):\n",
    "            dp2[i][0] = 1 \n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,m+1):\n",
    "                dp1[i][j] = (dp1[max(0, i-4)][j]+dp1[max(0,i-3)][j-1]+dp1[max(0,i-2)][max(0,j-2)]+dp1[i-1][max(0,j-3)]) * 0.25 \n",
    "                dp2[i][j] = (dp2[max(0, i-4)][j]+dp2[max(0,i-3)][j-1]+dp2[max(0,i-2)][max(0,j-2)]+dp2[i-1][max(0,j-3)]) * 0.25 \n",
    "        return 1 - (dp1[m][m] * 0.5 + dp2[m][m])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "\n",
    "        def dfs(cur_a, cur_b, cur_p, cache):\n",
    "\n",
    "            if (cur_a, cur_b, cur_p) in cache:\n",
    "                return cache[(cur_a, cur_b, cur_p)]\n",
    "\n",
    "            same_p = 0.0\n",
    "            a_first_p = 0.0\n",
    "\n",
    "            dirs = [(-100, 0), (-75, -25), (-50, -50), (-25, -75)]\n",
    "\n",
    "            for a_diff, b_diff in dirs:\n",
    "                next_a = cur_a + a_diff\n",
    "                next_b = cur_b + b_diff\n",
    "                if next_a <= 0 and next_b <= 0:\n",
    "                    same_p += 0.25 * cur_p\n",
    "                elif next_a <= 0:\n",
    "                    a_first_p += 0.25 * cur_p\n",
    "                elif next_b <= 0:\n",
    "                    continue\n",
    "                else:\n",
    "                    next_same_p, next_a_first_p = dfs(next_a, next_b, cur_p * 0.25, cache)\n",
    "                    a_first_p += next_a_first_p\n",
    "                    same_p += next_same_p\n",
    "\n",
    "            cache[(cur_a, cur_b, cur_p)] = (same_p, a_first_p)\n",
    "            return same_p, a_first_p\n",
    "        \n",
    "        n = min(n, 5000)\n",
    "        same_p, a_first_p = dfs(n, n, 1.0, {})\n",
    "        return a_first_p + 0.5 * same_p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        if n>10000:\n",
    "            return 1;\n",
    "        @cache\n",
    "        def func(a,b):\n",
    "            if a==0 and b==0:\n",
    "                return 0.5;\n",
    "            if a==0:\n",
    "                return 1;\n",
    "            if b==0:\n",
    "                return 0;\n",
    "            return 0.25*(func(max(a-100,0),b)+func(max(a-75,0),max(b-25,0))+func(max(a-50,0),max(b-50,0))+func(max(a-25,0),max(b-75,0)));\n",
    "        return func(n,n);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        def relu(x):\n",
    "            return max(x, 0.)\n",
    "\n",
    "        @cache\n",
    "        def divide(a, b):\n",
    "            if a + b == 0:\n",
    "                return 0.5\n",
    "            if a == 0:\n",
    "                return 1.\n",
    "            if b == 0:\n",
    "                return 0.\n",
    "            \n",
    "            return 0.25*divide(relu(a-100), b) + 0.25*divide(relu(a-75),relu(b-25)) + \\\n",
    "                    0.25*divide(relu(a-50), relu(b-50)) + 0.25*divide(relu(a-25),relu(b-75))\n",
    "        \n",
    "        if n >= 10000:\n",
    "            return 1.\n",
    "        return divide(n, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        # 笑死 tnnd\n",
    "        # 超时怎么办呢\n",
    "        # 因为 > 几k之后A先分配完的概率无限趋近于1 所以直接n大的时候不用算直接返回1就行 我日你的哥\n",
    "        if n > 4800:\n",
    "            return 1.0\n",
    "\n",
    "        if n > 4275:\n",
    "            return 0.99999\n",
    "\n",
    "        if n % 25:\n",
    "            n = ((n // 25) + 1) * 25\n",
    "\n",
    "        my_dict_A = {}\n",
    "        my_dict_AB = {}\n",
    "        # initial\n",
    "        my_dict_AB[(0, 0)] = 1\n",
    "        my_dict_A[(0, 0)] = 0\n",
    "        for i in range(25, n+25, 25):\n",
    "            my_dict_A[(0, i)] = 1\n",
    "            my_dict_AB[(0, i)] = 0\n",
    "            my_dict_A[(i, 0)] = 0\n",
    "            my_dict_AB[(i, 0)] = 0\n",
    "        \n",
    "        dis = ((100, 0), (75, 25), (50, 50), (25, 75))\n",
    "        \n",
    "        for i in range(25, n+25, 25):\n",
    "            for j in range(25, n+25, 25):\n",
    "                p_a, p_ab = 0, 0\n",
    "                for d in dis:\n",
    "                    tmpa, tmpb = max(i - d[0], 0), max(j - d[1], 0)\n",
    "                    p_a += 0.25 * my_dict_A[(tmpa, tmpb)]\n",
    "                    p_ab += 0.25 * my_dict_AB[(tmpa, tmpb)]\n",
    "                my_dict_A[(i, j)] = p_a\n",
    "                my_dict_AB[(i, j)] = p_ab\n",
    "        \n",
    "                \n",
    "        return my_dict_A[(n, n)] + 0.5 * my_dict_AB[(n, n)]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "      def relu(x):\n",
    "        return max(x, 0)\n",
    "\n",
    "      n = min(200, (n + 24) // 25)\n",
    "      m = n + 1\n",
    "      dp = [[0] * m for _ in range(m)]\n",
    "      dp[0] = [0.5] + [1.0] * n\n",
    "\n",
    "      for i in range(1, m):\n",
    "        for j in range(1, m):\n",
    "          dp[i][j] = 0.25 * (\n",
    "            dp[relu(i - 4)][j] +\n",
    "            dp[relu(i - 3)][j - 1] +\n",
    "            dp[relu(i - 2)][relu(j - 2)] +\n",
    "            dp[i - 1][relu(j - 3)]\n",
    "          )\n",
    "\n",
    "      print(dp)\n",
    "      return dp[n][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def soupServings(self, n: int) -> float:\n",
    "        if n > 5000:\n",
    "            return 1\n",
    "\n",
    "        '''\n",
    "        第一个返回值是a分配完的概率\n",
    "        第二个是同时分配完的概率\n",
    "        '''\n",
    "        @cache\n",
    "        def dfs(a, b):\n",
    "            res1 = res2 = 0\n",
    "            for da, db in ((100,0),(75,25),(50,50),(25,75)):\n",
    "                if a - da <=0 and b - db <= 0:\n",
    "                    res2 += 0.25\n",
    "                elif a - da <=0:\n",
    "                    res1 += 0.25\n",
    "                elif a-da >0 and b-db >0:\n",
    "                    p1, p2 = dfs(a-da,b-db)\n",
    "                    res1 += 0.25 * p1\n",
    "                    res2 += 0.25 * p2\n",
    "            \n",
    "            return res1, res2\n",
    "        \n",
    "        ans1, ans2 = dfs(n,n)\n",
    "        return ans1 + ans2/2"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
